package com.gjx.leetcode;

import java.util.Arrays;

//31. 下一个排列
//
//实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
//
//如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
//
//必须原地修改，只允许使用额外常数空间。
//
//以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
//1,2,3 → 1,3,2
//3,2,1 → 1,2,3
//1,1,5 → 1,5,1


public class Solution031 {
	public void nextPermutation(int[] nums) {
        
		int maxIndex = findMax(nums);
		
		if (maxIndex == 0) {
			reverse(nums, 0, nums.length-1);
			return;
		} 
		
		int secondMax = find(nums, maxIndex, nums.length-1, nums[maxIndex-1]);
		swap(nums, maxIndex-1, secondMax);
		reverse(nums, maxIndex, nums.length-1);
		
		
    }
	
	private int findMax(int[] nums) {
		int max = nums[nums.length-1];
		int res = nums.length - 1;
		for (int i=nums.length-2; i>=0; i--) {
			if (nums[i] >= max) {
				max = nums[i];
				res = i;
			} else {
				return res;
			}
		}
		return res;
	}
	
	private int find(int[] nums, int left, int right, int value) {
		
		int res = left;
		
		for (int i=left+1; i<=right; i++) {
			if (value < nums[i]) {
				res = i;
			}
		}
		
		return res;
		
	}
	
	
	private void reverse(int[] nums, int left, int right) {
		while (left < right) {
			swap(nums, left, right);
			left++;
			right--;
		}
	}
	
	private void swap(int[] nums, int i, int j) {
		int t = nums[i];
		nums[i] = nums[j];
		nums[j] = t;
	}
	
	public static void main(String[] args) {
		new Solution031().nextPermutation(new int[]{5,1,1});
	}
	
}
